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