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 = TREE_CHAIN (phi);
  62       remove_phi_arg (phi, e->src);
  63     }
  64
  65   remove_edge (e);
  66 }
  67
  68 /* Remove remove the corresponding arguments from the PHI nodes
  69    in E's 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 = TREE_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 the definition of SSA_NAME at block BB is malformed.
 106
 107    STMT is the statement where SSA_NAME is created.
 108
 109    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 110       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 111       block in that array slot contains the definition of SSA_NAME.  */
 112
 113 static bool
 114 verify_def (basic_block bb, basic_block *definition_block, tree ssa_name,
 115             tree stmt)
 116 {
 117   bool err = false;
 118
 119   if (TREE_CODE (ssa_name) != SSA_NAME)
 120     {
 121       error ("Expected an SSA_NAME object");
 122       debug_generic_stmt (ssa_name);
 123       debug_generic_stmt (stmt);
 124     }
 125
 126   if (definition_block[SSA_NAME_VERSION (ssa_name)])
 127     {
 128       error ("SSA_NAME created in two different blocks %i and %i",
 129              definition_block[SSA_NAME_VERSION (ssa_name)]->index, bb->index);
 130       fprintf (stderr, "SSA_NAME: ");
 131       debug_generic_stmt (ssa_name);
 132       debug_generic_stmt (stmt);
 133       err = true;
 134     }
 135
 136   definition_block[SSA_NAME_VERSION (ssa_name)] = bb;
 137
 138   if (SSA_NAME_DEF_STMT (ssa_name) != stmt)
 139     {
 140       error ("SSA_NAME_DEF_STMT is wrong");
 141       fprintf (stderr, "SSA_NAME: ");
 142       debug_generic_stmt (ssa_name);
 143       fprintf (stderr, "Expected definition statement:\n");
 144       debug_generic_stmt (SSA_NAME_DEF_STMT (ssa_name));
 145       fprintf (stderr, "\nActual definition statement:\n");
 146       debug_generic_stmt (stmt);
 147       err = true;
 148     }
 149
 150   return err;
 151 }
 152
 153
 154 /* Return true if the use of SSA_NAME at statement STMT in block BB is
 155    malformed.
 156
 157    DEF_BB is the block where SSA_NAME was found to be created.
 158
 159    IDOM contains immediate dominator information for the flowgraph.
 160
 161    CHECK_ABNORMAL is true if the caller wants to check whether this use
 162       is flowing through an abnormal edge (only used when checking PHI
 163       arguments).  */
 164
 165 static bool
 166 verify_use (basic_block bb, basic_block def_bb, tree ssa_name,
 167             tree stmt, bool check_abnormal)
 168 {
 169   bool err = false;
 170
 171   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (ssa_name)))
 172     ; /* Nothing to do.  */
 173   else if (!def_bb)
 174     {
 175       error ("Missing definition");
 176       err = true;
 177     }
 178   else if (bb != def_bb
 179            && !dominated_by_p (CDI_DOMINATORS, bb, def_bb))
 180     {
 181       error ("Definition in block %i does not dominate use in block %i",
 182              def_bb->index, bb->index);
 183       err = true;
 184     }
 185
 186   if (check_abnormal
 187       && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (ssa_name))
 188     {
 189       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI should be set");
 190       err = true;
 191     }
 192
 193   if (err)
 194     {
 195       fprintf (stderr, "for SSA_NAME: ");
 196       debug_generic_stmt (ssa_name);
 197       fprintf (stderr, "in statement:\n");
 198       debug_generic_stmt (stmt);
 199     }
 200
 201   return err;
 202 }
 203
 204
 205 /* Return true if any of the arguments for PHI node PHI at block BB is
 206    malformed.
 207
 208    IDOM contains immediate dominator information for the flowgraph.
 209
 210    DEFINITION_BLOCK is an array of basic blocks indexed by SSA_NAME version
 211       numbers.  If DEFINITION_BLOCK[SSA_NAME_VERSION] is set, it means that the
 212       block in that array slot contains the definition of SSA_NAME.  */
 213
 214 static bool
 215 verify_phi_args (tree phi, basic_block bb, basic_block *definition_block)
 216 {
 217   edge e;
 218   bool err = false;
 219   int i, phi_num_args = PHI_NUM_ARGS (phi);
 220
 221   /* Mark all the incoming edges.  */
 222   for (e = bb->pred; e; e = e->pred_next)
 223     e->aux = (void *) 1;
 224
 225   for (i = 0; i < phi_num_args; i++)
 226     {
 227       tree op = PHI_ARG_DEF (phi, i);
 228
 229       e = PHI_ARG_EDGE (phi, i);
 230
 231       if (TREE_CODE (op) == SSA_NAME)
 232         err |= verify_use (e->src, definition_block[SSA_NAME_VERSION (op)], op,
 233                            phi, e->flags & EDGE_ABNORMAL);
 234
 235       if (e->dest != bb)
 236         {
 237           error ("Wrong edge %d->%d for PHI argument\n",
 238                  e->src->index, e->dest->index, bb->index);
 239           err = true;
 240         }
 241
 242       if (e->aux == (void *) 0)
 243         {
 244           error ("PHI argument flowing through dead edge %d->%d\n",
 245                  e->src->index, e->dest->index);
 246           err = true;
 247         }
 248
 249       if (e->aux == (void *) 2)
 250         {
 251           error ("PHI argument duplicated for edge %d->%d\n", e->src->index,
 252                  e->dest->index);
 253           err = true;
 254         }
 255
 256       if (err)
 257         {
 258           fprintf (stderr, "PHI argument\n");
 259           debug_generic_stmt (op);
 260         }
 261
 262       e->aux = (void *) 2;
 263     }
 264
 265   for (e = bb->pred; e; e = e->pred_next)
 266     {
 267       if (e->aux != (void *) 2)
 268         {
 269           error ("No argument flowing through edge %d->%d\n", e->src->index,
 270                  e->dest->index);
 271           err = true;
 272         }
 273       e->aux = (void *) 0;
 274     }
 275
 276   if (err)
 277     {
 278       fprintf (stderr, "for PHI node\n");
 279       debug_generic_stmt (phi);
 280     }
 281
 282
 283   return err;
 284 }
 285
 286
 287 /* Verify common invariants in the SSA web.
 288    TODO: verify the variable annotations.  */
 289
 290 void
 291 verify_ssa (void)
 292 {
 293   bool err = false;
 294   basic_block bb;
 295   basic_block *definition_block = xcalloc (highest_ssa_version,
 296                                            sizeof (basic_block));
 297
 298   timevar_push (TV_TREE_SSA_VERIFY);
 299
 300   calculate_dominance_info (CDI_DOMINATORS);
 301
 302   /* Verify and register all the SSA_NAME definitions found in the
 303      function.  */
 304   FOR_EACH_BB (bb)
 305     {
 306       tree phi;
 307       block_stmt_iterator bsi;
 308
 309       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 310         err |= verify_def (bb, definition_block, PHI_RESULT (phi), phi);
 311
 312       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 313         {
 314           tree stmt;
 315           stmt_ann_t ann;
 316           unsigned int j;
 317           vdef_optype vdefs;
 318           def_optype defs;
 319
 320           stmt = bsi_stmt (bsi);
 321           ann = stmt_ann (stmt);
 322           get_stmt_operands (stmt);
 323
 324           vdefs = VDEF_OPS (ann);
 325           for (j = 0; j < NUM_VDEFS (vdefs); j++)
 326             {
 327               tree op = VDEF_RESULT (vdefs, j);
 328               if (is_gimple_reg (op))
 329                 {
 330                   error ("Found a virtual definition for a GIMPLE register");
 331                   debug_generic_stmt (op);
 332                   debug_generic_stmt (stmt);
 333                   err = true;
 334                 }
 335               err |= verify_def (bb, definition_block, op, stmt);
 336             }
 337
 338           defs = DEF_OPS (ann);
 339           for (j = 0; j < NUM_DEFS (defs); j++)
 340             {
 341               tree op = DEF_OP (defs, j);
 342               if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op))
 343                 {
 344                   error ("Found a real definition for a non-GIMPLE register");
 345                   debug_generic_stmt (op);
 346                   debug_generic_stmt (stmt);
 347                   err = true;
 348                 }
 349               err |= verify_def (bb, definition_block, op, stmt);
 350             }
 351         }
 352     }
 353
 354
 355   /* Now verify all the uses and make sure they agree with the definitions
 356      found in the previous pass.  */
 357   FOR_EACH_BB (bb)
 358     {
 359       edge e;
 360       tree phi;
 361       block_stmt_iterator bsi;
 362
 363       /* Make sure that all edges have a clear 'aux' field.  */
 364       for (e = bb->pred; e; e = e->pred_next)
 365         {
 366           if (e->aux)
 367             {
 368               error ("AUX pointer initialized for edge %d->%d\n", e->src->index,
 369                       e->dest->index);
 370               err = true;
 371             }
 372         }
 373
 374       /* Verify the arguments for every PHI node in the block.  */
 375       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 376         err |= verify_phi_args (phi, bb, definition_block);
 377
 378       /* Now verify all the uses and vuses in every statement of the block.
 379
 380          Remember, the RHS of a VDEF is a use as well.  */
 381       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 382         {
 383           tree stmt = bsi_stmt (bsi);
 384           stmt_ann_t ann = stmt_ann (stmt);
 385           unsigned int j;
 386           vuse_optype vuses;
 387           vdef_optype vdefs;
 388           use_optype uses;
 389
 390           vuses = VUSE_OPS (ann);
 391           for (j = 0; j < NUM_VUSES (vuses); j++)
 392             {
 393               tree op = VUSE_OP (vuses, j);
 394
 395               if (is_gimple_reg (op))
 396                 {
 397                   error ("Found a virtual use for a GIMPLE register");
 398                   debug_generic_stmt (op);
 399                   debug_generic_stmt (stmt);
 400                   err = true;
 401                 }
 402               err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 403                                  op, stmt, false);
 404             }
 405
 406           vdefs = VDEF_OPS (ann);
 407           for (j = 0; j < NUM_VDEFS (vdefs); j++)
 408             {
 409               tree op = VDEF_OP (vdefs, j);
 410
 411               if (is_gimple_reg (op))
 412                 {
 413                   error ("Found a virtual use for a GIMPLE register");
 414                   debug_generic_stmt (op);
 415                   debug_generic_stmt (stmt);
 416                   err = true;
 417                 }
 418               err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 419                                  op, stmt, false);
 420             }
 421
 422           uses = USE_OPS (ann);
 423           for (j = 0; j < NUM_USES (uses); j++)
 424             {
 425               tree op = USE_OP (uses, j);
 426
 427               if (TREE_CODE (op) == SSA_NAME && !is_gimple_reg (op))
 428                 {
 429                   error ("Found a real use of a non-GIMPLE register");
 430                   debug_generic_stmt (op);
 431                   debug_generic_stmt (stmt);
 432                   err = true;
 433                 }
 434               err |= verify_use (bb, definition_block[SSA_NAME_VERSION (op)],
 435                                  op, stmt, false);
 436             }
 437         }
 438     }
 439
 440   free (definition_block);
 441
 442   timevar_pop (TV_TREE_SSA_VERIFY);
 443
 444   if (err)
 445     internal_error ("verify_ssa failed.");
 446 }
 447
 448
 449 /* Set the USED bit in the annotation for T.  */
 450
 451 void
 452 set_is_used (tree t)
 453 {
 454   while (1)
 455     {
 456       if (SSA_VAR_P (t))
 457         break;
 458
 459       switch (TREE_CODE (t))
 460         {
 461         case ARRAY_REF:
 462         case COMPONENT_REF:
 463         case REALPART_EXPR:
 464         case IMAGPART_EXPR:
 465         case BIT_FIELD_REF:
 466         case INDIRECT_REF:
 467           t = TREE_OPERAND (t, 0);
 468           break;
 469
 470         default:
 471           return;
 472         }
 473     }
 474
 475   if (TREE_CODE (t) == SSA_NAME)
 476     t = SSA_NAME_VAR (t);
 477
 478   var_ann (t)->used = 1;
 479 }
 480
 481
 482 /* Initialize global DFA and SSA structures.  */
 483
 484 void
 485 init_tree_ssa (void)
 486 {
 487   VARRAY_TREE_INIT (referenced_vars, 20, "referenced_vars");
 488   call_clobbered_vars = BITMAP_XMALLOC ();
 489   init_ssa_operands ();
 490   init_ssanames ();
 491   init_phinodes ();
 492   global_var = NULL_TREE;
 493   aliases_computed_p = false;
 494 }
 495
 496
 497 /* Deallocate memory associated with SSA data structures for FNDECL.  */
 498
 499 void
 500 delete_tree_ssa (void)
 501 {
 502   size_t i;
 503   basic_block bb;
 504   block_stmt_iterator bsi;
 505
 506   /* Remove annotations from every tree in the function.  */
 507   FOR_EACH_BB (bb)
 508     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 509       bsi_stmt (bsi)->common.ann = NULL;
 510
 511   /* Remove annotations from every referenced variable.  */
 512   if (referenced_vars)
 513     {
 514       for (i = 0; i < num_referenced_vars; i++)
 515         referenced_var (i)->common.ann = NULL;
 516       referenced_vars = NULL;
 517     }
 518
 519   fini_ssanames ();
 520   fini_phinodes ();
 521   fini_ssa_operands ();
 522
 523   global_var = NULL_TREE;
 524   BITMAP_XFREE (call_clobbered_vars);
 525   call_clobbered_vars = NULL;
 526   aliases_computed_p = false;
 527 }
 528
 529
 530 /* Return true if EXPR is a useless type conversion, otherwise return
 531    false.  */
 532
 533 bool
 534 tree_ssa_useless_type_conversion_1 (tree outer_type, tree inner_type)
 535 {
 536   /* If the inner and outer types are effectively the same, then
 537      strip the type conversion and enter the equivalence into
 538      the table.  */
 539   if (inner_type == outer_type
 540      || (lang_hooks.types_compatible_p (inner_type, outer_type)))
 541     return true;
 542
 543   /* If both types are pointers and the outer type is a (void *), then
 544      the conversion is not necessary.  The opposite is not true since
 545      that conversion would result in a loss of information if the
 546      equivalence was used.  Consider an indirect function call where
 547      we need to know the exact type of the function to correctly
 548      implement the ABI.  */
 549   else if (POINTER_TYPE_P (inner_type)
 550            && POINTER_TYPE_P (outer_type)
 551            && TREE_CODE (TREE_TYPE (outer_type)) == VOID_TYPE)
 552     return true;
 553
 554   /* Pointers and references are equivalent once we get to GENERIC,
 555      so strip conversions that just switch between them.  */
 556   else if (POINTER_TYPE_P (inner_type)
 557            && POINTER_TYPE_P (outer_type)
 558            && lang_hooks.types_compatible_p (inner_type, outer_type))
 559     return true;
 560
 561   /* If both the inner and outer types are integral types, then the
 562      conversion is not necessary if they have the same mode and
 563      signedness and precision.  Note that type _Bool can have size of
 564      4 (only happens on powerpc-darwin right now but can happen on any
 565      target that defines BOOL_TYPE_SIZE to be INT_TYPE_SIZE) and a
 566      precision of 1 while unsigned int is the same expect for a
 567      precision of 4 so testing of precision is necessary.  */
 568   else if (INTEGRAL_TYPE_P (inner_type)
 569            && INTEGRAL_TYPE_P (outer_type)
 570            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 571            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 572            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 573     return true;
 574
 575   /* Recurse for complex types.  */
 576   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 577            && TREE_CODE (outer_type) == COMPLEX_TYPE
 578            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 579                                                   TREE_TYPE (inner_type)))
 580     return true;
 581
 582   return false;
 583 }
 584
 585 /* Return true if EXPR is a useless type conversion, otherwise return
 586    false.  */
 587
 588 bool
 589 tree_ssa_useless_type_conversion (tree expr)
 590 {
 591   /* If we have an assignment that merely uses a NOP_EXPR to change
 592      the top of the RHS to the type of the LHS and the type conversion
 593      is "safe", then strip away the type conversion so that we can
 594      enter LHS = RHS into the const_and_copies table.  */
 595   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
 596     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 597                                                TREE_TYPE (TREE_OPERAND (expr,
 598                                                                         0)));
 599
 600
 601   return false;
 602 }
 603
 604
 605 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 606    described in walk_use_def_chains.  VISITED is a bitmap used to mark
 607    visited SSA_NAMEs to avoid infinite loops.  */
 608
 609 static bool
 610 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 611                        bitmap visited)
 612 {
 613   tree def_stmt;
 614
 615   if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
 616     return false;
 617
 618   bitmap_set_bit (visited, SSA_NAME_VERSION (var));
 619
 620   def_stmt = SSA_NAME_DEF_STMT (var);
 621
 622   if (TREE_CODE (def_stmt) != PHI_NODE)
 623     {
 624       /* If we reached the end of the use-def chain, call FN.  */
 625       return (*fn) (var, def_stmt, data);
 626     }
 627   else
 628     {
 629       int i;
 630
 631       /* Otherwise, follow use-def links out of each PHI argument and call
 632          FN after visiting each one.  */
 633       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 634         {
 635           tree arg = PHI_ARG_DEF (def_stmt, i);
 636           if (TREE_CODE (arg) == SSA_NAME
 637               && walk_use_def_chains_1 (arg, fn, data, visited))
 638             return true;
 639
 640           if ((*fn) (arg, def_stmt, data))
 641             return true;
 642         }
 643     }
 644   return false;
 645 }
 646
 647
 648
 649 /* Walk use-def chains starting at the SSA variable VAR.  Call function FN
 650    at each reaching definition found.  FN takes three arguments: VAR, its
 651    defining statement (DEF_STMT) and a generic pointer to whatever state
 652    information that FN may want to maintain (DATA).  FN is able to stop the
 653    walk by returning true, otherwise in order to continue the walk, FN
 654    should return false.
 655
 656    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 657    different.  For each argument ARG of the PHI node, this function will:
 658
 659         1- Walk the use-def chains for ARG.
 660         2- Call (*FN) (ARG, PHI, DATA).
 661
 662    Note how the first argument to FN is no longer the original variable
 663    VAR, but the PHI argument currently being examined.  If FN wants to get
 664    at VAR, it should call PHI_RESULT (PHI).  */
 665
 666 void
 667 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data)
 668 {
 669   tree def_stmt;
 670
 671 #if defined ENABLE_CHECKING
 672   if (TREE_CODE (var) != SSA_NAME)
 673     abort ();
 674 #endif
 675
 676   def_stmt = SSA_NAME_DEF_STMT (var);
 677
 678   /* We only need to recurse if the reaching definition comes from a PHI
 679      node.  */
 680   if (TREE_CODE (def_stmt) != PHI_NODE)
 681     (*fn) (var, def_stmt, data);
 682   else
 683     {
 684       bitmap visited = BITMAP_XMALLOC ();
 685       walk_use_def_chains_1 (var, fn, data, visited);
 686       BITMAP_XFREE (visited);
 687     }
 688 }
 689
 690
 691 /* Replaces immediate uses of VAR by REPL.  */
 692
 693 static void
 694 replace_immediate_uses (tree var, tree repl)
 695 {
 696   use_optype uses;
 697   vuse_optype vuses;
 698   vdef_optype vdefs;
 699   int i, j, n;
 700   dataflow_t df;
 701   tree stmt;
 702   stmt_ann_t ann;
 703
 704   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 705   n = num_immediate_uses (df);
 706
 707   for (i = 0; i < n; i++)
 708     {
 709       stmt = immediate_use (df, i);
 710       ann = stmt_ann (stmt);
 711
 712       if (TREE_CODE (stmt) == PHI_NODE)
 713         {
 714           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 715             if (PHI_ARG_DEF (stmt, j) == var)
 716               {
 717                 PHI_ARG_DEF (stmt, j) = repl;
 718                 if (TREE_CODE (repl) == SSA_NAME
 719                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 720                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 721               }
 722
 723           continue;
 724         }
 725
 726       get_stmt_operands (stmt);
 727       if (is_gimple_reg (SSA_NAME_VAR (var)))
 728         {
 729           uses = USE_OPS (ann);
 730           for (j = 0; j < (int) NUM_USES (uses); j++)
 731             if (USE_OP (uses, j) == var)
 732               propagate_value (USE_OP_PTR (uses, j), repl);
 733         }
 734       else
 735         {
 736           vuses = VUSE_OPS (ann);
 737           for (j = 0; j < (int) NUM_VUSES (vuses); j++)
 738             if (VUSE_OP (vuses, j) == var)
 739               propagate_value (VUSE_OP_PTR (vuses, j), repl);
 740
 741           vdefs = VDEF_OPS (ann);
 742           for (j = 0; j < (int) NUM_VDEFS (vdefs); j++)
 743             if (VDEF_OP (vdefs, j) == var)
 744               propagate_value (VDEF_OP_PTR (vdefs, j), repl);
 745         }
 746
 747       modify_stmt (stmt);
 748
 749       /* If REPL is a pointer, it may have different memory tags associated
 750          with it.  For instance, VAR may have had a name tag while REPL
 751          only had a type tag.  In these cases, the virtual operands (if
 752          any) in the statement will refer to different symbols which need
 753          to be renamed.  */
 754       if (POINTER_TYPE_P (TREE_TYPE (repl)))
 755         mark_new_vars_to_rename (stmt, vars_to_rename);
 756     }
 757 }
 758
 759 /* Raises value of phi node PHI by joining it with VAL.  Processes immediate
 760    uses of PHI recursively.  */
 761
 762 static void
 763 raise_value (tree phi, tree val, tree *eq_to)
 764 {
 765   int i, n;
 766   tree var = PHI_RESULT (phi), stmt;
 767   int ver = SSA_NAME_VERSION (var);
 768   dataflow_t df;
 769
 770   if (eq_to[ver] == var)
 771     return;
 772
 773   switch (TREE_CODE (val))
 774     {
 775     case SSA_NAME:
 776     case REAL_CST:
 777     case COMPLEX_CST:
 778       break;
 779     case INTEGER_CST:
 780       if (TREE_CODE (TREE_TYPE (var)) != POINTER_TYPE)
 781         break;
 782
 783     default:
 784       /* Do not propagate pointer constants.  This might require folding
 785          things like *&foo and rewriting the ssa, which is not worth the
 786          trouble.  */
 787       val = var;
 788     }
 789
 790   if (eq_to[ver])
 791     {
 792       if (operand_equal_p (eq_to[ver], val, 0))
 793         return;
 794
 795       eq_to[ver] = var;
 796     }
 797   else
 798     eq_to[ver] = val;
 799
 800   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 801   n = num_immediate_uses (df);
 802
 803   for (i = 0; i < n; i++)
 804     {
 805       stmt = immediate_use (df, i);
 806
 807       if (TREE_CODE (stmt) != PHI_NODE)
 808         continue;
 809
 810       raise_value (stmt, eq_to[ver], eq_to);
 811     }
 812 }
 813
 814 /* Removes redundant phi nodes.
 815
 816    A redundant PHI node is a PHI node where all of its PHI arguments
 817    are the same value, excluding any PHI arguments which are the same
 818    as the PHI result.
 819
 820    A redundant PHI node is effectively a copy, so we forward copy propagate
 821    which removes all uses of the destination of the PHI node then
 822    finally we delete the redundant PHI node.
 823
 824    Note that if we can not copy propagate the PHI node, then the PHI
 825    will not be removed.  Thus we do not have to worry about dependencies
 826    between PHIs and the problems serializing PHIs into copies creates.
 827
 828    The most important effect of this pass is to remove degenerate PHI
 829    nodes created by removing unreachable code.  */
 830
 831 static void
 832 kill_redundant_phi_nodes (void)
 833 {
 834   tree *eq_to, *ssa_names;
 835   unsigned i, ver, aver;
 836   basic_block bb;
 837   tree phi, t, stmt, var;
 838
 839   /* The EQ_TO array holds the current value of the ssa name in the
 840      lattice:
 841
 842           top
 843          / | \
 844      const   variables
 845          \ | /
 846         bottom
 847
 848      Bottom is represented by NULL and top by the variable itself.
 849
 850      Once the dataflow stabilizes, we know that the phi nodes we need to keep
 851      are exactly those with top as their result.
 852
 853      The remaining phi nodes have their uses replaced with their value
 854      in the lattice and the phi node itself is removed.  */
 855   eq_to = xcalloc (highest_ssa_version, sizeof (tree));
 856
 857   /* The SSA_NAMES array holds each SSA_NAME node we encounter
 858      in a PHI node (indexed by ssa version number).
 859
 860      One could argue that the SSA_NAME manager ought to provide a
 861      generic interface to get at the SSA_NAME node for a given
 862      ssa version number.  */
 863   ssa_names = xcalloc (highest_ssa_version, sizeof (tree));
 864
 865   /* We have had cases where computing immediate uses takes a
 866      significant amount of compile time.  If we run into such
 867      problems here, we may want to only compute immediate uses for
 868      a subset of all the SSA_NAMEs instead of computing it for
 869      all of the SSA_NAMEs.  */
 870   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 871
 872   FOR_EACH_BB (bb)
 873     {
 874       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 875         {
 876           var = PHI_RESULT (phi);
 877           ver = SSA_NAME_VERSION (var);
 878           ssa_names[ver] = var;
 879
 880           for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 881             {
 882               t = PHI_ARG_DEF (phi, i);
 883
 884               if (TREE_CODE (t) != SSA_NAME)
 885                 {
 886                   raise_value (phi, t, eq_to);
 887                   continue;
 888                 }
 889
 890               stmt = SSA_NAME_DEF_STMT (t);
 891               aver = SSA_NAME_VERSION (t);
 892               ssa_names[aver] = t;
 893
 894               /* If the defining statement for this argument is not a
 895                  phi node or the argument is associated with an abnormal
 896                  edge, then we need to recursively start the forward
 897                  dataflow starting with PHI.  */
 898               if (TREE_CODE (stmt) != PHI_NODE
 899                   || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
 900                 {
 901                   eq_to[aver] = t;
 902                   raise_value (phi, t, eq_to);
 903                 }
 904             }
 905         }
 906     }
 907
 908   /* Now propagate the values.  */
 909   for (i = 0; i < highest_ssa_version; i++)
 910     if (eq_to[i]
 911         && eq_to[i] != ssa_names[i])
 912       replace_immediate_uses (ssa_names[i], eq_to[i]);
 913
 914   /* And remove the dead phis.  */
 915   for (i = 0; i < highest_ssa_version; i++)
 916     if (eq_to[i]
 917         && eq_to[i] != ssa_names[i])
 918       {
 919         stmt = SSA_NAME_DEF_STMT (ssa_names[i]);
 920         remove_phi_node (stmt, 0, bb_for_stmt (stmt));
 921       }
 922
 923   free_df ();
 924   free (eq_to);
 925   free (ssa_names);
 926 }
 927
 928 struct tree_opt_pass pass_redundant_phi =
 929 {
 930   "redphi",                             /* name */
 931   NULL,                                 /* gate */
 932   kill_redundant_phi_nodes,             /* execute */
 933   NULL,                                 /* sub */
 934   NULL,                                 /* next */
 935   0,                                    /* static_pass_number */
 936   0,                                    /* tv_id */
 937   PROP_cfg | PROP_ssa,                  /* properties_required */
 938   0,                                    /* properties_provided */
 939   0,                                    /* properties_destroyed */
 940   0,                                    /* todo_flags_start */
 941   TODO_dump_func | TODO_rename_vars
 942     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
 943 };
 944 \f
 945 /* Emit warnings for uninitialized variables.  This is done in two passes.
 946
 947    The first pass notices real uses of SSA names with default definitions.
 948    Such uses are unconditionally uninitialized, and we can be certain that
 949    such a use is a mistake.  This pass is run before most optimizations,
 950    so that we catch as many as we can.
 951
 952    The second pass follows PHI nodes to find uses that are potentially
 953    uninitialized.  In this case we can't necessarily prove that the use
 954    is really uninitialized.  This pass is run after most optimizations,
 955    so that we thread as many jumps and possible, and delete as much dead
 956    code as possible, in order to reduce false positives.  We also look
 957    again for plain uninitialized variables, since optimization may have
 958    changed conditionally uninitialized to unconditionally uninitialized.  */
 959
 960 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
 961    warning text is in MSGID and LOCUS may contain a location or be null.  */
 962
 963 static void
 964 warn_uninit (tree t, const char *msgid, location_t *locus)
 965 {
 966   tree var = SSA_NAME_VAR (t);
 967   tree def = SSA_NAME_DEF_STMT (t);
 968
 969   /* Default uses (indicated by an empty definition statement),
 970      are uninitialized.  */
 971   if (!IS_EMPTY_STMT (def))
 972     return;
 973
 974   /* Except for PARMs of course, which are always initialized.  */
 975   if (TREE_CODE (var) == PARM_DECL)
 976     return;
 977
 978   /* Hard register variables get their initial value from the ether.  */
 979   if (DECL_HARD_REGISTER (var))
 980     return;
 981
 982   /* TREE_NO_WARNING either means we already warned, or the front end
 983      wishes to suppress the warning.  */
 984   if (TREE_NO_WARNING (var))
 985     return;
 986
 987   if (!locus)
 988     locus = &DECL_SOURCE_LOCATION (var);
 989   warning (msgid, locus, var);
 990   TREE_NO_WARNING (var) = 1;
 991 }
 992
 993 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
 994    and warn about them.  */
 995
 996 static tree
 997 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
 998 {
 999   location_t *locus = data;
1000   tree t = *tp;
1001
1002   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1003   if (TREE_CODE (t) == SSA_NAME)
1004     {
1005       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1006       *walk_subtrees = 0;
1007     }
1008   else if (DECL_P (t) || TYPE_P (t))
1009     *walk_subtrees = 0;
1010
1011   return NULL_TREE;
1012 }
1013
1014 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1015    and warn about them.  */
1016
1017 static void
1018 warn_uninitialized_phi (tree phi)
1019 {
1020   int i, n = PHI_NUM_ARGS (phi);
1021
1022   /* Don't look at memory tags.  */
1023   if (!is_gimple_reg (PHI_RESULT (phi)))
1024     return;
1025
1026   for (i = 0; i < n; ++i)
1027     {
1028       tree op = PHI_ARG_DEF (phi, i);
1029       if (TREE_CODE (op) == SSA_NAME)
1030         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1031                      NULL);
1032     }
1033 }
1034
1035 static void
1036 execute_early_warn_uninitialized (void)
1037 {
1038   block_stmt_iterator bsi;
1039   basic_block bb;
1040
1041   FOR_EACH_BB (bb)
1042     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1043       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1044                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1045 }
1046
1047 static void
1048 execute_late_warn_uninitialized (void)
1049 {
1050   basic_block bb;
1051   tree phi;
1052
1053   /* Re-do the plain uninitialized variable check, as optimization may have
1054      straightened control flow.  Do this first so that we don't accidentally
1055      get a "may be" warning when we'd have seen an "is" warning later.  */
1056   execute_early_warn_uninitialized ();
1057
1058   FOR_EACH_BB (bb)
1059     for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1060       warn_uninitialized_phi (phi);
1061 }
1062
1063 static bool
1064 gate_warn_uninitialized (void)
1065 {
1066   return warn_uninitialized != 0;
1067 }
1068
1069 struct tree_opt_pass pass_early_warn_uninitialized =
1070 {
1071   NULL,                                 /* name */
1072   gate_warn_uninitialized,              /* gate */
1073   execute_early_warn_uninitialized,     /* execute */
1074   NULL,                                 /* sub */
1075   NULL,                                 /* next */
1076   0,                                    /* static_pass_number */
1077   0,                                    /* tv_id */
1078   PROP_ssa,                             /* properties_required */
1079   0,                                    /* properties_provided */
1080   0,                                    /* properties_destroyed */
1081   0,                                    /* todo_flags_start */
1082   0                                     /* todo_flags_finish */
1083 };
1084
1085 struct tree_opt_pass pass_late_warn_uninitialized =
1086 {
1087   NULL,                                 /* name */
1088   gate_warn_uninitialized,              /* gate */
1089   execute_late_warn_uninitialized,      /* execute */
1090   NULL,                                 /* sub */
1091   NULL,                                 /* next */
1092   0,                                    /* static_pass_number */
1093   0,                                    /* tv_id */
1094   PROP_ssa,                             /* properties_required */
1095   0,                                    /* properties_provided */
1096   0,                                    /* properties_destroyed */
1097   0,                                    /* todo_flags_start */
1098   0                                     /* todo_flags_finish */
1099 };