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 (TREE_TYPE (inner_type),
 559                                              TREE_TYPE (outer_type)))
 560     return true;
 561
 562   /* If both the inner and outer types are integral types, then the
 563      conversion is not necessary if they have the same mode and
 564      signedness and precision.  Note that type _Bool can have size of
 565      4 (only happens on powerpc-darwin right now but can happen on any
 566      target that defines BOOL_TYPE_SIZE to be INT_TYPE_SIZE) and a
 567      precision of 1 while unsigned int is the same expect for a
 568      precision of 4 so testing of precision is necessary.  */
 569   else if (INTEGRAL_TYPE_P (inner_type)
 570            && INTEGRAL_TYPE_P (outer_type)
 571            && TYPE_MODE (inner_type) == TYPE_MODE (outer_type)
 572            && TYPE_UNSIGNED (inner_type) == TYPE_UNSIGNED (outer_type)
 573            && TYPE_PRECISION (inner_type) == TYPE_PRECISION (outer_type))
 574     return true;
 575
 576   /* Recurse for complex types.  */
 577   else if (TREE_CODE (inner_type) == COMPLEX_TYPE
 578            && TREE_CODE (outer_type) == COMPLEX_TYPE
 579            && tree_ssa_useless_type_conversion_1 (TREE_TYPE (outer_type),
 580                                                   TREE_TYPE (inner_type)))
 581     return true;
 582
 583   return false;
 584 }
 585
 586 /* Return true if EXPR is a useless type conversion, otherwise return
 587    false.  */
 588
 589 bool
 590 tree_ssa_useless_type_conversion (tree expr)
 591 {
 592   /* If we have an assignment that merely uses a NOP_EXPR to change
 593      the top of the RHS to the type of the LHS and the type conversion
 594      is "safe", then strip away the type conversion so that we can
 595      enter LHS = RHS into the const_and_copies table.  */
 596   if (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
 597     return tree_ssa_useless_type_conversion_1 (TREE_TYPE (expr),
 598                                                TREE_TYPE (TREE_OPERAND (expr,
 599                                                                         0)));
 600
 601
 602   return false;
 603 }
 604
 605
 606 /* Internal helper for walk_use_def_chains.  VAR, FN and DATA are as
 607    described in walk_use_def_chains.  VISITED is a bitmap used to mark
 608    visited SSA_NAMEs to avoid infinite loops.  */
 609
 610 static bool
 611 walk_use_def_chains_1 (tree var, walk_use_def_chains_fn fn, void *data,
 612                        bitmap visited)
 613 {
 614   tree def_stmt;
 615
 616   if (bitmap_bit_p (visited, SSA_NAME_VERSION (var)))
 617     return false;
 618
 619   bitmap_set_bit (visited, SSA_NAME_VERSION (var));
 620
 621   def_stmt = SSA_NAME_DEF_STMT (var);
 622
 623   if (TREE_CODE (def_stmt) != PHI_NODE)
 624     {
 625       /* If we reached the end of the use-def chain, call FN.  */
 626       return (*fn) (var, def_stmt, data);
 627     }
 628   else
 629     {
 630       int i;
 631
 632       /* Otherwise, follow use-def links out of each PHI argument and call
 633          FN after visiting each one.  */
 634       for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++)
 635         {
 636           tree arg = PHI_ARG_DEF (def_stmt, i);
 637           if (TREE_CODE (arg) == SSA_NAME
 638               && walk_use_def_chains_1 (arg, fn, data, visited))
 639             return true;
 640
 641           if ((*fn) (arg, def_stmt, data))
 642             return true;
 643         }
 644     }
 645   return false;
 646 }
 647
 648
 649
 650 /* Walk use-def chains starting at the SSA variable VAR.  Call function FN
 651    at each reaching definition found.  FN takes three arguments: VAR, its
 652    defining statement (DEF_STMT) and a generic pointer to whatever state
 653    information that FN may want to maintain (DATA).  FN is able to stop the
 654    walk by returning true, otherwise in order to continue the walk, FN
 655    should return false.
 656
 657    Note, that if DEF_STMT is a PHI node, the semantics are slightly
 658    different.  For each argument ARG of the PHI node, this function will:
 659
 660         1- Walk the use-def chains for ARG.
 661         2- Call (*FN) (ARG, PHI, DATA).
 662
 663    Note how the first argument to FN is no longer the original variable
 664    VAR, but the PHI argument currently being examined.  If FN wants to get
 665    at VAR, it should call PHI_RESULT (PHI).  */
 666
 667 void
 668 walk_use_def_chains (tree var, walk_use_def_chains_fn fn, void *data)
 669 {
 670   tree def_stmt;
 671
 672 #if defined ENABLE_CHECKING
 673   if (TREE_CODE (var) != SSA_NAME)
 674     abort ();
 675 #endif
 676
 677   def_stmt = SSA_NAME_DEF_STMT (var);
 678
 679   /* We only need to recurse if the reaching definition comes from a PHI
 680      node.  */
 681   if (TREE_CODE (def_stmt) != PHI_NODE)
 682     (*fn) (var, def_stmt, data);
 683   else
 684     {
 685       bitmap visited = BITMAP_XMALLOC ();
 686       walk_use_def_chains_1 (var, fn, data, visited);
 687       BITMAP_XFREE (visited);
 688     }
 689 }
 690
 691
 692 /* Replaces immediate uses of VAR by REPL.  */
 693
 694 static void
 695 replace_immediate_uses (tree var, tree repl)
 696 {
 697   use_optype uses;
 698   vuse_optype vuses;
 699   vdef_optype vdefs;
 700   int i, j, n;
 701   dataflow_t df;
 702   tree stmt;
 703   stmt_ann_t ann;
 704
 705   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 706   n = num_immediate_uses (df);
 707
 708   for (i = 0; i < n; i++)
 709     {
 710       stmt = immediate_use (df, i);
 711       ann = stmt_ann (stmt);
 712
 713       if (TREE_CODE (stmt) == PHI_NODE)
 714         {
 715           for (j = 0; j < PHI_NUM_ARGS (stmt); j++)
 716             if (PHI_ARG_DEF (stmt, j) == var)
 717               {
 718                 PHI_ARG_DEF (stmt, j) = repl;
 719                 if (TREE_CODE (repl) == SSA_NAME
 720                     && PHI_ARG_EDGE (stmt, j)->flags & EDGE_ABNORMAL)
 721                   SSA_NAME_OCCURS_IN_ABNORMAL_PHI (repl) = 1;
 722               }
 723
 724           continue;
 725         }
 726
 727       get_stmt_operands (stmt);
 728       if (is_gimple_reg (SSA_NAME_VAR (var)))
 729         {
 730           uses = USE_OPS (ann);
 731           for (j = 0; j < (int) NUM_USES (uses); j++)
 732             if (USE_OP (uses, j) == var)
 733               propagate_value (USE_OP_PTR (uses, j), repl);
 734         }
 735       else
 736         {
 737           vuses = VUSE_OPS (ann);
 738           for (j = 0; j < (int) NUM_VUSES (vuses); j++)
 739             if (VUSE_OP (vuses, j) == var)
 740               propagate_value (VUSE_OP_PTR (vuses, j), repl);
 741
 742           vdefs = VDEF_OPS (ann);
 743           for (j = 0; j < (int) NUM_VDEFS (vdefs); j++)
 744             if (VDEF_OP (vdefs, j) == var)
 745               propagate_value (VDEF_OP_PTR (vdefs, j), repl);
 746         }
 747
 748       modify_stmt (stmt);
 749
 750       /* If REPL is a pointer, it may have different memory tags associated
 751          with it.  For instance, VAR may have had a name tag while REPL
 752          only had a type tag.  In these cases, the virtual operands (if
 753          any) in the statement will refer to different symbols which need
 754          to be renamed.  */
 755       if (POINTER_TYPE_P (TREE_TYPE (repl)))
 756         mark_new_vars_to_rename (stmt, vars_to_rename);
 757     }
 758 }
 759
 760 /* Raises value of phi node PHI by joining it with VAL.  Processes immediate
 761    uses of PHI recursively.  */
 762
 763 static void
 764 raise_value (tree phi, tree val, tree *eq_to)
 765 {
 766   int i, n;
 767   tree var = PHI_RESULT (phi), stmt;
 768   int ver = SSA_NAME_VERSION (var);
 769   dataflow_t df;
 770
 771   if (eq_to[ver] == var)
 772     return;
 773
 774   switch (TREE_CODE (val))
 775     {
 776     case SSA_NAME:
 777     case REAL_CST:
 778     case COMPLEX_CST:
 779       break;
 780     case INTEGER_CST:
 781       if (TREE_CODE (TREE_TYPE (var)) != POINTER_TYPE)
 782         break;
 783
 784     default:
 785       /* Do not propagate pointer constants.  This might require folding
 786          things like *&foo and rewriting the ssa, which is not worth the
 787          trouble.  */
 788       val = var;
 789     }
 790
 791   if (eq_to[ver])
 792     {
 793       if (operand_equal_p (eq_to[ver], val, 0))
 794         return;
 795
 796       eq_to[ver] = var;
 797     }
 798   else
 799     eq_to[ver] = val;
 800
 801   df = get_immediate_uses (SSA_NAME_DEF_STMT (var));
 802   n = num_immediate_uses (df);
 803
 804   for (i = 0; i < n; i++)
 805     {
 806       stmt = immediate_use (df, i);
 807
 808       if (TREE_CODE (stmt) != PHI_NODE)
 809         continue;
 810
 811       raise_value (stmt, eq_to[ver], eq_to);
 812     }
 813 }
 814
 815 /* Removes redundant phi nodes.
 816
 817    A redundant PHI node is a PHI node where all of its PHI arguments
 818    are the same value, excluding any PHI arguments which are the same
 819    as the PHI result.
 820
 821    A redundant PHI node is effectively a copy, so we forward copy propagate
 822    which removes all uses of the destination of the PHI node then
 823    finally we delete the redundant PHI node.
 824
 825    Note that if we can not copy propagate the PHI node, then the PHI
 826    will not be removed.  Thus we do not have to worry about dependencies
 827    between PHIs and the problems serializing PHIs into copies creates.
 828
 829    The most important effect of this pass is to remove degenerate PHI
 830    nodes created by removing unreachable code.  */
 831
 832 static void
 833 kill_redundant_phi_nodes (void)
 834 {
 835   tree *eq_to, *ssa_names;
 836   unsigned i, ver, aver;
 837   basic_block bb;
 838   tree phi, t, stmt, var;
 839
 840   /* The EQ_TO array holds the current value of the ssa name in the
 841      lattice:
 842
 843           top
 844          / | \
 845      const   variables
 846          \ | /
 847         bottom
 848
 849      Bottom is represented by NULL and top by the variable itself.
 850
 851      Once the dataflow stabilizes, we know that the phi nodes we need to keep
 852      are exactly those with top as their result.
 853
 854      The remaining phi nodes have their uses replaced with their value
 855      in the lattice and the phi node itself is removed.  */
 856   eq_to = xcalloc (highest_ssa_version, sizeof (tree));
 857
 858   /* The SSA_NAMES array holds each SSA_NAME node we encounter
 859      in a PHI node (indexed by ssa version number).
 860
 861      One could argue that the SSA_NAME manager ought to provide a
 862      generic interface to get at the SSA_NAME node for a given
 863      ssa version number.  */
 864   ssa_names = xcalloc (highest_ssa_version, sizeof (tree));
 865
 866   /* We have had cases where computing immediate uses takes a
 867      significant amount of compile time.  If we run into such
 868      problems here, we may want to only compute immediate uses for
 869      a subset of all the SSA_NAMEs instead of computing it for
 870      all of the SSA_NAMEs.  */
 871   compute_immediate_uses (TDFA_USE_OPS | TDFA_USE_VOPS, NULL);
 872
 873   FOR_EACH_BB (bb)
 874     {
 875       for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
 876         {
 877           var = PHI_RESULT (phi);
 878           ver = SSA_NAME_VERSION (var);
 879           ssa_names[ver] = var;
 880
 881           for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
 882             {
 883               t = PHI_ARG_DEF (phi, i);
 884
 885               if (TREE_CODE (t) != SSA_NAME)
 886                 {
 887                   raise_value (phi, t, eq_to);
 888                   continue;
 889                 }
 890
 891               stmt = SSA_NAME_DEF_STMT (t);
 892               aver = SSA_NAME_VERSION (t);
 893               ssa_names[aver] = t;
 894
 895               /* If the defining statement for this argument is not a
 896                  phi node or the argument is associated with an abnormal
 897                  edge, then we need to recursively start the forward
 898                  dataflow starting with PHI.  */
 899               if (TREE_CODE (stmt) != PHI_NODE
 900                   || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (t))
 901                 {
 902                   eq_to[aver] = t;
 903                   raise_value (phi, t, eq_to);
 904                 }
 905             }
 906         }
 907     }
 908
 909   /* Now propagate the values.  */
 910   for (i = 0; i < highest_ssa_version; i++)
 911     if (eq_to[i]
 912         && eq_to[i] != ssa_names[i])
 913       replace_immediate_uses (ssa_names[i], eq_to[i]);
 914
 915   /* And remove the dead phis.  */
 916   for (i = 0; i < highest_ssa_version; i++)
 917     if (eq_to[i]
 918         && eq_to[i] != ssa_names[i])
 919       {
 920         stmt = SSA_NAME_DEF_STMT (ssa_names[i]);
 921         remove_phi_node (stmt, 0, bb_for_stmt (stmt));
 922       }
 923
 924   free_df ();
 925   free (eq_to);
 926   free (ssa_names);
 927 }
 928
 929 struct tree_opt_pass pass_redundant_phi =
 930 {
 931   "redphi",                             /* name */
 932   NULL,                                 /* gate */
 933   kill_redundant_phi_nodes,             /* execute */
 934   NULL,                                 /* sub */
 935   NULL,                                 /* next */
 936   0,                                    /* static_pass_number */
 937   0,                                    /* tv_id */
 938   PROP_cfg | PROP_ssa,                  /* properties_required */
 939   0,                                    /* properties_provided */
 940   0,                                    /* properties_destroyed */
 941   0,                                    /* todo_flags_start */
 942   TODO_dump_func | TODO_rename_vars
 943     | TODO_ggc_collect | TODO_verify_ssa /* todo_flags_finish */
 944 };
 945 \f
 946 /* Emit warnings for uninitialized variables.  This is done in two passes.
 947
 948    The first pass notices real uses of SSA names with default definitions.
 949    Such uses are unconditionally uninitialized, and we can be certain that
 950    such a use is a mistake.  This pass is run before most optimizations,
 951    so that we catch as many as we can.
 952
 953    The second pass follows PHI nodes to find uses that are potentially
 954    uninitialized.  In this case we can't necessarily prove that the use
 955    is really uninitialized.  This pass is run after most optimizations,
 956    so that we thread as many jumps and possible, and delete as much dead
 957    code as possible, in order to reduce false positives.  We also look
 958    again for plain uninitialized variables, since optimization may have
 959    changed conditionally uninitialized to unconditionally uninitialized.  */
 960
 961 /* Emit a warning for T, an SSA_NAME, being uninitialized.  The exact
 962    warning text is in MSGID and LOCUS may contain a location or be null.  */
 963
 964 static void
 965 warn_uninit (tree t, const char *msgid, location_t *locus)
 966 {
 967   tree var = SSA_NAME_VAR (t);
 968   tree def = SSA_NAME_DEF_STMT (t);
 969
 970   /* Default uses (indicated by an empty definition statement),
 971      are uninitialized.  */
 972   if (!IS_EMPTY_STMT (def))
 973     return;
 974
 975   /* Except for PARMs of course, which are always initialized.  */
 976   if (TREE_CODE (var) == PARM_DECL)
 977     return;
 978
 979   /* Hard register variables get their initial value from the ether.  */
 980   if (DECL_HARD_REGISTER (var))
 981     return;
 982
 983   /* TREE_NO_WARNING either means we already warned, or the front end
 984      wishes to suppress the warning.  */
 985   if (TREE_NO_WARNING (var))
 986     return;
 987
 988   if (!locus)
 989     locus = &DECL_SOURCE_LOCATION (var);
 990   warning (msgid, locus, var);
 991   TREE_NO_WARNING (var) = 1;
 992 }
 993
 994 /* Called via walk_tree, look for SSA_NAMEs that have empty definitions
 995    and warn about them.  */
 996
 997 static tree
 998 warn_uninitialized_var (tree *tp, int *walk_subtrees, void *data)
 999 {
1000   location_t *locus = data;
1001   tree t = *tp;
1002
1003   /* We only do data flow with SSA_NAMEs, so that's all we can warn about.  */
1004   if (TREE_CODE (t) == SSA_NAME)
1005     {
1006       warn_uninit (t, "%H'%D' is used uninitialized in this function", locus);
1007       *walk_subtrees = 0;
1008     }
1009   else if (DECL_P (t) || TYPE_P (t))
1010     *walk_subtrees = 0;
1011
1012   return NULL_TREE;
1013 }
1014
1015 /* Look for inputs to PHI that are SSA_NAMEs that have empty definitions
1016    and warn about them.  */
1017
1018 static void
1019 warn_uninitialized_phi (tree phi)
1020 {
1021   int i, n = PHI_NUM_ARGS (phi);
1022
1023   /* Don't look at memory tags.  */
1024   if (!is_gimple_reg (PHI_RESULT (phi)))
1025     return;
1026
1027   for (i = 0; i < n; ++i)
1028     {
1029       tree op = PHI_ARG_DEF (phi, i);
1030       if (TREE_CODE (op) == SSA_NAME)
1031         warn_uninit (op, "%H'%D' may be used uninitialized in this function",
1032                      NULL);
1033     }
1034 }
1035
1036 static void
1037 execute_early_warn_uninitialized (void)
1038 {
1039   block_stmt_iterator bsi;
1040   basic_block bb;
1041
1042   FOR_EACH_BB (bb)
1043     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1044       walk_tree (bsi_stmt_ptr (bsi), warn_uninitialized_var,
1045                  EXPR_LOCUS (bsi_stmt (bsi)), NULL);
1046 }
1047
1048 static void
1049 execute_late_warn_uninitialized (void)
1050 {
1051   basic_block bb;
1052   tree phi;
1053
1054   /* Re-do the plain uninitialized variable check, as optimization may have
1055      straightened control flow.  Do this first so that we don't accidentally
1056      get a "may be" warning when we'd have seen an "is" warning later.  */
1057   execute_early_warn_uninitialized ();
1058
1059   FOR_EACH_BB (bb)
1060     for (phi = phi_nodes (bb); phi; phi = TREE_CHAIN (phi))
1061       warn_uninitialized_phi (phi);
1062 }
1063
1064 static bool
1065 gate_warn_uninitialized (void)
1066 {
1067   return warn_uninitialized != 0;
1068 }
1069
1070 struct tree_opt_pass pass_early_warn_uninitialized =
1071 {
1072   NULL,                                 /* name */
1073   gate_warn_uninitialized,              /* gate */
1074   execute_early_warn_uninitialized,     /* execute */
1075   NULL,                                 /* sub */
1076   NULL,                                 /* next */
1077   0,                                    /* static_pass_number */
1078   0,                                    /* tv_id */
1079   PROP_ssa,                             /* properties_required */
1080   0,                                    /* properties_provided */
1081   0,                                    /* properties_destroyed */
1082   0,                                    /* todo_flags_start */
1083   0                                     /* todo_flags_finish */
1084 };
1085
1086 struct tree_opt_pass pass_late_warn_uninitialized =
1087 {
1088   NULL,                                 /* name */
1089   gate_warn_uninitialized,              /* gate */
1090   execute_late_warn_uninitialized,      /* execute */
1091   NULL,                                 /* sub */
1092   NULL,                                 /* next */
1093   0,                                    /* static_pass_number */
1094   0,                                    /* tv_id */
1095   PROP_ssa,                             /* properties_required */
1096   0,                                    /* properties_provided */
1097   0,                                    /* properties_destroyed */
1098   0,                                    /* todo_flags_start */
1099   0                                     /* todo_flags_finish */
1100 };